/**
 * 
 */
package tree;

import utils.CreateUtils;
import utils.PrintUtils;

/**
 * @author Michael
 * 
 */
public class LargestDistanceBetweenTwoNodes {

	public static int distance(Node<Integer> root) {
		return largestDistance(root)[0];

	}

	// [0]: largest distance, [1]: height of tree
	public static int[] largestDistance(Node<Integer> root) {
		if (root == null) {
			return new int[] { 0, 0 };
		}

		int[] pair = largestDistance(root.left);
		int leftDistance = pair[0];
		int leftHeight = pair[1];

		pair = largestDistance(root.right);
		int rightDistance = pair[0];
		int rightHeight = pair[1];

		int maxDistance = Math.max(leftHeight + rightHeight,
				Math.max(leftDistance, rightDistance));
		int maxHeight = 1 + Math.max(leftHeight, rightHeight);

		return new int[] { maxDistance, maxHeight };
	}

	private TreeNodeStatus getTreeNodeStatus(TreeNode node) {
		TreeNodeStatus status = new TreeNodeStatus();
		if (node == null) {
			status.maxLength = 0;
			status.maxDepth = 0;
		} else if (node.left == null && node.right == null) {
			status.maxLength = 1;
			status.maxDepth = 1;
		} else {
			TreeNodeStatus leftStatus = getTreeNodeStatus(node.left);
			TreeNodeStatus rightStatus = getTreeNodeStatus(node.right);
			status.maxDepth = Math.max(leftStatus.maxDepth + 1,
					rightStatus.maxDepth + 1);
			status.maxLength = Math.max(leftStatus.maxLength,
					rightStatus.maxLength);
			status.maxLength = Math.max(status.maxLength, leftStatus.maxDepth
					+ rightStatus.maxDepth + 1);
		}

		return status;
	}

	class TreeNodeStatus {
		int maxLength;
		int maxDepth;
	}

	public int longestPath(TreeNode root) {
		TreeNodeStatus status = getTreeNodeStatus(root);

		return status.maxLength;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Node<Integer> root = CreateUtils.bstWithTenNodes();
		PrintUtils.printBinaryTree(root);
		System.out.println(distance(root));

	}

	/**
	 * 
	 */
	public LargestDistanceBetweenTwoNodes() {
		// TODO Auto-generated constructor stub
	}

}
